package 二叉树;

import java.util.PriorityQueue;

public class JZ54二叉搜索树的第k大节点 {

    /**
     * 给定一棵二叉搜索树，请找出其中第k大的节点。
     *
     * 示例 1:
     * 输入: root = [3,1,4,null,2], k = 1
     *    3
     *   / \
     *  1   4
     *   \
     *    2
     * 输出: 4
     *
     * 示例 2:
     * 输入: root = [5,3,6,2,4,null,null,1], k = 3
     *        5
     *       / \
     *      3   6
     *     / \
     *    2   4
     *   /
     *  1
     * 输出: 4
     *  
     * 限制：
     * 1 ≤ k ≤ 二叉搜索树元素个数
     */

    private int index;
    private boolean isResult;
    private int result;

    public int kthLargest(TreeNode root, int k) {
        midFor(root,k-1);
        return result;
    }

    private void midFor(TreeNode node,int k) {

        if(isResult){
            return;
        }

        if(node==null){
            return;
        }

        midFor(node.right,k);

        if(index==k){
            result=node.val;
            isResult=true;
            index++;
            return;
        }

        index++;

        midFor(node.left,k);

    }

    public static void main(String[] args) {
        JZ54二叉搜索树的第k大节点 jz=new JZ54二叉搜索树的第k大节点();
        TreeNode treeNode = TreeNode.getNodeByArr(new Integer[]{3, 1, 4, null, 2});
        treeNode.printNode();
        int result = jz.kthLargest(treeNode, 3);
        System.out.println(result);
    }

}
